Distributed computer systems are made up of a number of communicating nodes. The nodes connect various devices, such as processors, mass storage devices, printers, terminals, etc., to the computer system. The devices may communicate with each other, through the nodes, regardless of the physical proximity of the devices and/or the nodes. Nodes located relatively close together may communicate over a local area network. Nodes located some distance apart may communicate over other communications lines, such as telephone lines.
The nodes, as well as the connected devices and associated processes, data bases and other (logical) objects, collectively referred to herein as objects, must be uniquely labeled or named such that the objects can be positively identified throughout the entire distributed system. Otherwise, communications meant for a particular object may be sent to the wrong object and thus lost, or data may be deleted from or added to the wrong object due to a mistaken identity.
In a distributed system a centralized label-generator may be used to ensure that each object is given a unique label, commonly referred to as an identifier. Every time an identifier is required, a request for one is sent over the network communication lines to the central generator, and the generator formulates and returns an identifier for the object. Communication line availability, for sending the request to the generator and returning the generated identifier to the object, or the availability of the generator, may limit the availability of the identifiers and may cause delays. Various objects may require the generation of identifiers relatively quickly, or even simultaneously. Thus using a central generator and waiting for the return of an identifier, even with communication lines that are immediately available, may cause delays.
To avoid such delays and ensure more robust identifier availability, a number of decentralized generators may be used. The decentralized generators are capable of simultaneously generating identifiers. However, some method of ensuring that the generated identifiers are unique throughout the entire system must be used.
One such method requires communication between the generators such that each generator is "informed" of the identifiers already assigned. Delays and limitations similar to those arising from using a centralized generator may result each time the generators communicate.
In another method, identifiers are created by concatenating the identifier of the nodes associated with the objects and the then current time read from a clock associated with the node. Identifiers created simultaneously for objects associated with different nodes will thus differ at least by the node identifiers, and identifiers created for objects associated with the same node at different times will differ by the difference in the current time. Thus the generators using this method for creating identifiers need not communicate.
Delays in creating identifiers may still be experienced, however, when a particular generator is instructed to generate identifiers at a rate which is faster than the resolution of the associated node clock. If the generator generates the identifiers without a delay, duplicate identifiers will be generated. Thus a method of generating unique identifiers at a rate which is faster than the resolution of the associated node clock is desirable.
Duplicate identifiers may also be created using this method when the clocks are re-set, for example, during a system re-boot. If the node clocks are set to times preceding their previous current times, identifiers generated thereafter may be duplicates of earlier ones. Similarly, if the system is re-configured, a node may become newly associated with a clock which is operating behind the time of the previously associated clock, and duplicate identifiers may be created. Thus a decentralized generating method which produces unique identifiers regardless of changes in associated clocks and/or system configuration is desirable.